package jm.algorithm.sort;

/**
 * @Description 快速排序实现
 * @date 2022/5/7 9:13
 */
public class QuickSort<T extends Comparable<T>> extends Sort<T> {


    @Override
    protected void sort() {
        sort(0,arr.length);
    }

    /**
     * 对 [begin, end) 范围内元素进行快速排序
     * @param begin
     * @param end
     */
    private void sort(int begin, int end){
        if (end - begin < 2) return;

        // 确定轴点位置
        int mid = pivot(begin, end);

        // 对子序列进行快速排序
        sort(begin,mid);
        sort(mid + 1, end);
    }

    /**
     * 构造 [begin, end) 范围的轴点元素
     * @param begin
     * @param end
     * @return 轴点元素位置
     */
    private int pivot(int begin, int end){

        // 随机一个元素与begin位置元素交换
        swap(begin, begin + (int)(Math.random() * (end - begin)));

        // 备份目标元素
        T pivot = arr[begin];

        // 让 end 指向最后一个元素的索引
        end--;

        while (begin < end){
            while (begin < end) {
                if (cmp(pivot, arr[end]) < 0) {
                    end--;
                } else {
                    arr[begin] = arr[end];
                    begin++;
                    break; // 跳出转向
                }
            }

            while (begin < end) {
                if (cmp(pivot, arr[begin]) > 0) {
                    begin++;
                } else {
                    arr[end] = arr[begin];
                    end--;
                    break; // 跳出转向
                }
            }
        }
        // 重新赋值备份元素
        arr[begin] = pivot;
        // 轴点元素位置
        return begin;
    }
}
